#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

long long factorial(int n)
{
	long long res = 1;
	for (int i = 2; i <= n; ++i)
	{
		res *= i;
	}
	return res;
}

long long n_treaps_with_heigth_less_then_h(int n_pairs, int treap_h)
{
	if (n_pairs <= treap_h)
		return factorial(n_pairs);

	if (treap_h < 0)
		return 0;

	long long n_trees = 0;
	for (int i = 0; i < n_pairs; ++i)
	{
		n_trees += n_treaps_with_heigth_less_then_h(i, treap_h-1) * n_treaps_with_heigth_less_then_h(n_pairs-i-1, treap_h-1);
	}
	
	return n_trees;
}

long long n_treaps_of_height_h(int n_pairs, int treap_h)
{
	if (treap_h == 0)
	{
		if (n_pairs == 1)
			return 1;
		else
			return 0;
	}

	long long n_trees = 0;
	for (int i = 0; i < n_pairs; ++i)
	{
		n_trees += n_treaps_of_height_h(i, treap_h-1) * n_treaps_with_heigth_less_then_h(n_pairs-i-1, treap_h-1) + 
			n_treaps_of_height_h(n_pairs-i-1, treap_h-1) * n_treaps_with_heigth_less_then_h(i, treap_h-1) + 
			n_treaps_of_height_h(i, treap_h-1) * n_treaps_of_height_h(n_pairs-i-1, treap_h-1);
	}

	return n_trees;
}

double count_prob(int n_pairs, int treap_h)
{
	return static_cast<double>(n_treaps_of_height_h(n_pairs, treap_h)) / factorial(n_pairs);
}

void main()
{
	int n_pairs, treap_h;
	cout << "Input number of pairs and treap length: ";
	cin >> n_pairs >> treap_h;

	cout << "Probability of treap to have height " << treap_h << " is equal to " << count_prob(n_pairs, treap_h);
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.get();
}